{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import gcd\n",
    "\n",
    "def factorization(n):\n",
    "\n",
    "    factors = []\n",
    "\n",
    "    def get_factor(n):\n",
    "        x_fixed = 2\n",
    "        cycle_size = 2\n",
    "        x = 2\n",
    "        factor = 1\n",
    "\n",
    "        while factor == 1:\n",
    "            for count in range(cycle_size):\n",
    "                if factor > 1: break\n",
    "                x = (x * x + 1) % n\n",
    "                factor = gcd(x - x_fixed, n)\n",
    "\n",
    "            cycle_size *= 2\n",
    "            x_fixed = x\n",
    "\n",
    "        return factor\n",
    "\n",
    "    while n > 1:\n",
    "        next = get_factor(n)\n",
    "        factors.append(next)\n",
    "        n //= next\n",
    "\n",
    "    return factors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorization(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 2]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorization(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Not prime. Divisible by: 2\n",
      "4 is prime\n"
     ]
    }
   ],
   "source": [
    "from math import sqrt\n",
    "\n",
    "n = 4\n",
    "sn = int(sqrt(n))\n",
    "for x in range(2,sn+1):\n",
    "    if n%x == 0:\n",
    "        print('Not prime. Divisible by: '+str(x))\n",
    "print(str(n)+' is prime')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import sqrt\n",
    "\n",
    "def get_the_num(n):\n",
    "    sn = int(sqrt(n))\n",
    "    for x in range(2,sn+1):\n",
    "        if n%x == 0:\n",
    "            return x\n",
    "    return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_the_num(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {0: 423, 1: 2130, 2: 1377, 3: 2880, 4: 93, 5: 633, 6: 516, 7: 708, 8: 201, 9: 108, 10: 138, 11: 189, 12: 288, 13: 126, 14: 27, 15: 48, 16: 42, 17: 39, 18: 24}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 3, 47] 423\n",
      "[3, 2, 5, 71] 2130\n",
      "[3, 3, 3, 3, 17] 1377\n",
      "[3, 3, 8, 8, 5] 2880\n",
      "[3, 31] 93\n",
      "[3, 211] 633\n",
      "[3, 4, 43] 516\n",
      "[3, 4, 59] 708\n",
      "[3, 67] 201\n",
      "[3, 3, 3, 4] 108\n",
      "[3, 2, 23] 138\n",
      "[3, 3, 3, 7] 189\n",
      "[3, 3, 8, 4] 288\n",
      "[3, 3, 2, 7] 126\n",
      "[3, 3, 3] 27\n",
      "[3, 8, 2] 48\n",
      "[3, 2, 7] 42\n",
      "[3, 13] 39\n",
      "[3, 8] 24\n"
     ]
    }
   ],
   "source": [
    "for _, v in d.items():\n",
    "    print(factorization(v), v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {0: 180, 1: 3890, 2: 910, 3: 855, 4: 1105, 5: 385, 6: 1230, 7: 120, 8: 275, 9: 155, 10: 235, 11: 190, 12: 150, 13: 90, 14: 50, 15: 60, 16: 25, 17: 40, 18: 40, 19: 15}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 5, 389]\n",
      "0 3890\n",
      "[3, 2, 5, 41]\n",
      "0 1230\n",
      "[5, 13, 17]\n",
      "0 1105\n",
      "[2, 7, 5, 13]\n",
      "0 910\n",
      "[3, 3, 5, 19]\n",
      "0 855\n",
      "[7, 11, 5]\n",
      "0 385\n",
      "[11, 25]\n",
      "0 275\n",
      "[5, 47]\n",
      "0 235\n",
      "[2, 5, 19]\n",
      "0 190\n",
      "[3, 3, 4, 5]\n",
      "0 180\n",
      "[31, 5]\n",
      "0 155\n",
      "[3, 2, 25]\n",
      "0 150\n",
      "[3, 8, 5]\n",
      "0 120\n",
      "[3, 3, 2, 5]\n",
      "0 90\n",
      "[3, 4, 5]\n",
      "0 60\n",
      "[2, 25]\n",
      "0 50\n",
      "[8, 5]\n",
      "0 40\n",
      "[8, 5]\n",
      "0 40\n",
      "[25]\n",
      "0 25\n",
      "[3, 5]\n",
      "0 15\n"
     ]
    }
   ],
   "source": [
    "for v in sorted(d.values(), reverse=True):\n",
    "    #print(list(sorted(factorization(v) + [get_the_num(v)])), v)\n",
    "    print(factorization(v))\n",
    "    print(v%5, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [1,2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "l.sort(reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 2, 1]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_the_num(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards\n",
    "\n",
    "\n",
    "Runtime: 124 ms, faster than 94.54% of Python3 online submissions for X of a Kind in a Deck of Cards.\n",
    "Memory Usage: 14.4 MB, less than 13.57% of Python3 online submissions for X of a Kind in a Deck of Cards.\n",
    "\n",
    "\n",
    "```python\n",
    "from math import gcd\n",
    "\n",
    "def factorization(n):\n",
    "    factors = []\n",
    "\n",
    "    def get_factor(n):\n",
    "        x_fixed = 2\n",
    "        cycle_size = 2\n",
    "        x = 2\n",
    "        factor = 1\n",
    "\n",
    "        while factor == 1:\n",
    "            for count in range(cycle_size):\n",
    "                if factor > 1: break\n",
    "                x = (x * x + 1) % n\n",
    "                factor = gcd(x - x_fixed, n)\n",
    "\n",
    "            cycle_size *= 2\n",
    "            x_fixed = x\n",
    "\n",
    "        return factor\n",
    "\n",
    "    while n > 1:\n",
    "        next = get_factor(n)\n",
    "        factors.append(next)\n",
    "        n //= next\n",
    "\n",
    "    return factors\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hasGroupsSizeX(self, deck: List[int]) -> bool:\n",
    "        dict_ = {}\n",
    "        for i in deck:\n",
    "            if i in dict_.keys():\n",
    "                dict_[i] += 1\n",
    "            else:\n",
    "                dict_[i] = 1\n",
    "        #print(dict_)\n",
    "        if len(dict_.keys()) >= 1:\n",
    "            values = list(dict_.values())\n",
    "            values.sort(reverse=True)\n",
    "            common = factorization(values[0])\n",
    "            common.append(2)\n",
    "            for c in common:\n",
    "                if all(v%c==0 for v in values):\n",
    "                    return True\n",
    "        return False\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}